package num61;

/**
 * @author : DuJiabao
 * @Date : 2021/1/28 15:03
 * @Project : sword-finger-offer
 * @File : null.java
 * @Desc :给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。
 * https://leetcode-cn.com/problems/rotate-list/
 * 方法：快指针，直接走到倒数第一个结点，获取长度。然后取余计算出真正移动的步数。长度-步数-1计算出慢指针走的步数。掐头去尾，得到新的链表
 */
public class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if (k == 0 || head == null) return head;
        ListNode fast = head;
        int length = 1;
        // 走到链表尾，并获得链表长度
        while (fast.next != null) {
            fast = fast.next;
            length++;
        }
        // 真正链表需要旋转的步数
        k %= length;

        // 慢指针，走到新的链表尾
        ListNode slow = head;
        for (int i = 0; i < length - k - 1; i++) {
            slow = slow.next;
        }
        // 掐头去尾
        fast.next = head;
        head = slow.next;
        slow.next = null;
        return head;
    }
}
